package str;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 判断一个串在另外一个串中出现了几次
 * @date : 2023/8/22
 */
public class StringMatchCount {

    public static void main(String[] args) {
        String s = "abaabaabeca";
        String t = "abaa";
        System.out.println(getMatchCount(s,t));
    }

    private static int getMatchCount(String s,String t) {
        int i = 0,j=0,result=0;
        int[] next = getNext(t);
        System.out.println("nextj的值：" + Arrays.toString(next));
        while (i<s.length()) {
            if (j==-1||s.charAt(i) == t.charAt(j)) {
                j++;
                i++;
            } else {
                j=next[j];
            }
            if (j==t.length()) {
                result++;
                j=next[j-1];
            }
        }
        return result;
    }

    /**
     * 求next数组 next数组表示字符串前i-1个元素的最长相等前缀长度
     * @param t
     * @return
     */
    private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        int j=0,k=-1;
        next[0]=-1;
        // 因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
        // 所以最后一次经过while循环时j为t.length-2
        while (j<t.length()-1) {
            //对应字符匹配情况下，s与t指向同步后移
            if (k==-1 || t.charAt(j) == t.charAt(k)) {
                j++;
                k++;
                next[j]=k;
            } else {
                k=next[k];
            }
        }
        return next;
    }
}
